package com.heu.zth;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Set;

// Dijkstra + Heap
public class Dijkstra_Heap {
	private HashSet<Integer> doneSet = new HashSet<Integer>();
	private PriorityQueue<Car> priorityQueue = new PriorityQueue<>();
	
	void dijkstra(Car start) {
		start.setCurrentCost(0);
		priorityQueue.add(start);
		
		while(!priorityQueue.isEmpty()) {
			Car car = priorityQueue.poll();
			if (doneSet.contains(car.getId())) {
				continue;
			}
			
			doneSet.add(car.getId());
			
			HashMap<Car, Double> neighbors = car.getNeighbors();
			Set<Entry<Car, Double>> entries = neighbors.entrySet();
			for (Iterator<Entry<Car, Double>> iterator = entries.iterator(); iterator.hasNext();) {
				Entry<Car, Double> entry = iterator.next();
				Car c = entry.getKey();
				if (doneSet.contains(c.getId())) {
					continue;
				}
				
				double v = entry.getValue();
				if (c.getCurrentCost() > car.getCurrentCost() + v) {
					c.setCurrentCost(car.getCurrentCost() + v);
					c.parent = car;
					priorityQueue.remove(c);
					priorityQueue.add(c);
				}
			}
		}
	}
}